#ifndef QUADTREE_H
#define QUADTREE_H

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>
#include <unordered_map>
#include <set>
#include <omp.h>
#include <float.h>
#include<string>

using namespace std;

struct Point {
    int x, y;
};

struct Segment {
    Point a, b;
    int dx, dy;
    long long len2;
};

struct QueryPoint {
    double x, y;
};

struct Rect {
    int x0, y0, x1, y1;
    bool intersect(const Segment& seg) const;
};

class QuadNode {
public:
    Rect rect;
    vector<int> segs;
    vector<QuadNode*> children;
    bool is_leaf;

    QuadNode(Rect r);
    ~QuadNode();
};

class QuadTree {
private:
    QuadNode* root;
    // 存储所有线段（飞行线）的容器，索引即为线段ID（需+1转换）
    vector<Segment> segments;

    // 线段到四叉树节点的映射：记录每个线段被存储在哪些四叉树节点中
    // key: 线段在segments中的索引（内部ID）
    // value: 包含该线段的所有四叉树节点集合
    unordered_map<int, set<QuadNode*>> seg_to_nodes;

    // 四叉树的最大深度限制，防止无限递归分裂
    int max_depth;

    // 叶子节点允许的最大线段数量，超过此数量且未达最大深度时将分裂节点
    size_t max_segs_per_leaf;

    // 存储所有查询点的容器，按添加顺序存储
    vector<pair<int, int>> query_points;

    // 查询结果的存储映射
    // key: 查询点索引（在query_points中的位置）
    // value: 该查询点最近的(线段ID, 距离)结果对列表（历史记录）
    unordered_map<int, vector<pair<int, double>>> query_results;

    // 线段到查询点的反向映射：记录哪些查询点当前以该线段为最近线段
    // key: 线段ID（外部ID，即segments索引+1）
    // value: 依赖此线段的查询点索引集合
    unordered_map<int, set<int>> seg_to_queries;

    /**
    * 分裂四叉树节点（将当前节点划分为四个子区域）
     * @param node 要分裂的四叉树节点
     * @param depth 当前节点所在的深度
     */
    void split(QuadNode* node, int depth);

    /**
     * 将线段插入到指定四叉树节点中
     * @param seg_index 线段在segments中的索引（内部ID）
     * @param depth 当前节点深度
     * @param node 目标四叉树节点
     */
    void insert_into_node(int seg_index, int depth, QuadNode* node);

    /**
     * 计算点到矩形区域的最小平方距离（用于剪枝优化）
     * @param x 查询点x坐标
     * @param y 查询点y坐标
     * @param rect 矩形区域
     * @return 点到矩形的最小平方距离
     */
    double calc_dist_rect_sq(int x, int y, const Rect& rect) const;

    /**
     * 计算点到线段的精确平方距离
     * @param x 查询点x坐标
     * @param y 查询点y坐标
     * @param seg 目标线段
     * @return 点到线段的精确平方距离
     */
    double calc_dist_sq(int x, int y, const Segment& seg) const;

    /**
     * 内部查询方法：查找距离给定点最近的线段
     * @param x 查询点x坐标
     * @param y 查询点y坐标
     * @param query_idx 查询点索引（用于结果记录），-1表示临时查询
     * @return 包含(最近线段ID, 实际距离)的结果对
     */
    pair<int, double> query_internal(int x, int y, int query_idx);

public:
    QuadTree();
    ~QuadTree();


    /**
     * 添加一条新的飞行线段
     * @param x1 起点x坐标
     * @param y1 起点y坐标
     * @param x2 终点x坐标
     * @param y2 终点y坐标
     * @return 新线段的唯一ID（从1开始）
     *
     * 功能说明：
     * 1. 创建线段对象并计算其方向向量和长度平方
     * 2. 将线段添加到全局线段集合并获得内部索引
     * 3. 将线段插入四叉树结构
     * 4. 并行更新所有查询点，检查新线段是否更近
     * 5. 返回新线段的公开ID（内部索引+1）
     */
    int add_segment(int x1, int y1, int x2, int y2, vector<vector<wstring>>& QueryPointData);

    /**
     * 删除指定飞行线段
     * @param seg_id 要删除的线段ID（1开始）
     *
     * 功能说明：
     * 1. 将公开ID转换为内部索引
     * 2. 从seg_to_queries获取依赖此线段的查询点
     * 3. 从所有包含此线段的四叉树节点中移除该线段
     * 4. 并行重新计算所有受影响查询点的最近线段
     * 5. 输出每个受影响查询点的更新结果
     */
    void remove_segment(int seg_id, vector<vector<wstring>>& QueryPointData);


    /**
     * 查询距离给定点最近的飞行线
     * @param x 查询点x坐标
     * @param y 查询点y坐标
     * @return 包含(最近线段ID, 实际距离)的结果对
     *
     * 功能说明：
     * 1. 将查询点添加到全局查询点列表
     * 2. 使用优先队列实现最佳优先搜索
     * 3. 并行处理节点内线段距离计算
     * 4. 使用点到矩形距离剪枝优化搜索
     * 5. 记录查询结果用于后续更新
     */
    pair<int, double> query(int x, int y);

    /**
     * 打印当前所有查询点的最新结果
     *
     * 功能说明：
     * 1. 并行遍历所有查询点
     * 2. 对每个查询点获取其最新结果
     * 3. 输出格式：
     *    "查询点 [索引] (x,y): 飞行线ID: [ID] 距离大小:[距离]"
     * 4. 使用临界区保证输出完整性
     */
    void print_all_results();

    void clear();
};

#endif